package algotithm.leetcode.dp.hot.test5;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/10-17:36
 * @URL https://leetcode-cn.com/problems/longest-palindromic-substring/
 * @Title 5. 最长回文子串
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "babad";
        String str = solution.longestPalindrome(s);
        System.out.println(str);
    }

    public String longestPalindrome(String s) {
        if (s.length() == 0) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0;i < s.length(); i++) {
            int len1 = expandAroundCenter(s,i,i);
            int len2 = expandAroundCenter(s,i,i+1);
            int len = Math.max(len1,len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start,end+1);
    }

    public int expandAroundCenter(String s, int l, int r) {
        int i = l;
        int j = r;
        while (i >= 0 && j < s.length()) {
            if (s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            } else {
                break;
            }
        }
        return j - i - 1;
    }
}
